#include <iostream>
#include <stack>

using namespace std;

// 279 : perfect Square 无权有向图最短路径
// 时间复杂度: O(2^n)	空间复杂度: O(2^n)
class Solution {
public:
	// 返回多少个完全平方数
	int numSquares(int n) {
		queue<pair<int, int>> q;// (第几个数字， 经历了几个节点)
		q.push(make_pair(n, 0));
		while(!q.empty()){
			int num = q.front().first;			// 数字
			int step = q.front().second;
			q.pop();

			if(num == 0)
				return step;
			// 会将冗余数据推入数组
			for(int i = 0; num - i*i >= 0; i++)
				q.push(make_pair(num - i*i, step + 1));
		}

		throw invalid_argument("No Solution.");
	}
};

int main(){}
